package com.yan_jiu_sheng.LeetCodeHot100.AC;

import java.util.*;

/**
 * https://leetcode.cn/problems/merge-intervals/description/?envType=study-plan-v2&envId=top-100-liked
 * 通过
 *
 * @author yulongTian
 * @create 2024-05-28 11:01
 */
public class Test14 {
    public static void main(String[] args) {
//        int[][] intervals = {{1, 3}, {2, 6}, {15, 18}, {8, 10}};
//        int[][] intervals = {{1, 4}, {4, 5}};
//        int[][] intervals = {{1, 4}, {2, 3}};
        int[][] intervals = {{1, 4}, {2, 3}, {2, 6}, {7, 11}, {10, 12}, {8, 9}};
        System.out.println(Arrays.deepToString(merge(intervals)));
    }

    public static int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        List<int[]> list = new LinkedList<>();
        for (int i = 0; i < intervals.length; ) {
            int start = intervals[i][0];
            int end = intervals[i][1];
            int j = i + 1;
            while (true) {
                if (j >= intervals.length) {
                    int[] res = {start, end};
                    list.add(res);
                    i = j;
                    break;
                }
                int newStart = intervals[j][0];
                int newEnd = intervals[j][1];
                if (newStart <= end && newEnd >= end) {
                    end = intervals[j][1];
                    j++;
                } else if (newEnd < end) {
                    j++;
                } else {
                    int[] res = {start, end};
                    list.add(res);
                    i = j;
                    break;
                }

            }
        }
        int[][] res = new int[list.size()][2];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }


}
